package Leetcode.Stack;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author: kirito
 * @Date: 2024/4/22 12:21
 * @Description:
 * 找出最具竞争力的子序列
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。
 *
 * 数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。
 *
 * 在子序列 a 和子序列 b 第一个不相同的位置上，如果 a 中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。 例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， 4 小于 5 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [3,5,2,6], k = 2
 * 输出：[2,6]
 * 解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。
 * 示例 2：
 *
 * 输入：nums = [2,4,3,3,5,4,9,6], k = 4
 * 输出：[2,3,3,4]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * 0 <= nums[i] <= 109
 * 1 <= k <= nums.length
 */

public class mostCompetitive {
    public static void main(String[] args) {
        int[] arr = {2,4,3,3,5,4,9,6};
        int k = 4;
        System.out.println(Arrays.toString(new mostCompetitive().mostCompetitive(arr,k)));
    }

    /**
     * 满足数组长度为k
     * 尽可能小  从左到右尽可能小
     * 单调递增序列？同时得满足升序的数字还能组合成长度为k的数组
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] mostCompetitive(int[] nums, int k) {
        int len = nums.length;
        int[] ans = new int[k];
        Stack<Integer> stack = new Stack<>();
        int count = len - k;
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            while (!stack.isEmpty()
                    && num < nums[stack.peek()]
                    && count > 0) {
                count--;
                stack.pop();
            }
            stack.push(i);
        }
        for (int i = 0; i < k; i++) {
            ans[i] = nums[stack.get(i)];
        }
//        int index = k-1;
//        while (!stack.isEmpty()) {
//            if (index >= 0) {
//                ans[index] = nums[stack.pop()];
//                index--;
//            }else{
//                break;
//            }
//        }
        return ans;
    }
    public int[] mostCompetitive2(int[] nums, int k) {
        // 数组的长度
        int n = nums.length;
        // 由于最终结果需要长度为 n-k，所以调整 k 的值
        k = n - k;
        // 结果数组
        int[] res = new int[n];
        // 索引 j，用于构建结果数组
        int j = 0;
        // 遍历输入数组中的每个元素
        for(int x: nums){
            // 当 j > 0 且 k > 0 且当前元素 x 小于结果数组中的前一个元素时，
            // 说明当前元素不足以替换结果数组中的元素，需要尝试更小的元素
            while(j > 0 && k > 0 && x < res[j - 1]){
                j --;
                k --;
            }
            // 将当前元素放入结果数组
            res[j ++] = x;
        }
        // 由于我们只保留了 k 个最大的元素，所以结果数组实际上比输入数组短了 k 个元素
        // 创建一个新的数组，用来存放最终的结果
        int[] ans = new int[j - k];
        // 使用 System.arraycopy 方法将结果数组中的元素复制到新的数组中
        // 这里从索引 0 开始复制，复制长度为 j - k，即我们保留的元素数量
        System.arraycopy(res, 0, ans, 0, j - k);
        // 返回最终的数组
        return ans;
    }

}
